#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<stack>
#include<cmath>
#include<string>
#include<unordered_set>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first) return a.second % 2 > b.second % 2;
    return a.first > b.first;
}

void solve()
{
    int n; cin >> n;
    vector<pair<int, int>> arr(n + 5);
    for (int i = 1; i <= n; i++)
    {
        int temp; cin >> temp; arr[i] = pair<int, int>(temp, i);
    }
    sort(arr.begin() + 1, arr.begin() + n + 1, cmp);
    if (n % 2 == 0) cout << arr[1].first + n / 2 << endl;
    else
    {
        if (arr[1].second % 2) cout << arr[1].first + n / 2 + 1 << endl;
        else cout << arr[1].first + n / 2 << endl;
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}